package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.sun.corba.se.impl.orbutil.graph.Node;
import com.sun.javafx.image.IntPixelAccessor;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.datastructure.ListNode;

/*
 * 
 原题　
		Follow up for "Unique Paths":
	
	Now consider if some obstacles are added to the grids. How many unique paths would there be?
	
	An obstacle and empty space is marked as 1 and 0 respectively in the grid.
	
	For example,
	
	There is one obstacle in the middle of a 3x3 grid as illustrated below.
	
	[
	  [0,0,0],
	  [0,1,0],
	  [0,0,0]
	]

 题目大意

 解题思路

 @Type 动态规划
 * @Date 2017-10-01 22:26
 */
public class _062_Unique_Paths {

    public int uniquePaths(int m, int n) {
    	if (m==0 || n==0)	return 0;
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 1; i < m; i ++) {
        	dp[i][0] = 1;
        }
        for (int j = 1; j < n; j ++) {
        	dp[0][j] = 1;
        }
        for (int i = 1; i < m; i ++) {
        	for (int j = 1; j < n; j ++) {
        		dp[i][j] = dp[i-1][j] + dp[i][j-1];
        	}
        }
        return dp[m-1][n-1];
    }


	public static void main(String[] args) {
		_062_Unique_Paths obj = new _062_Unique_Paths();

		ListNode list = ListNode.newLinkList2();
		obj.uniquePaths(7, 3);
			

		// ListNode.traverse("remove", list);
	}

}
